package problem143;

import java.util.HashMap;

//143.重排链表
//https://leetcode.cn/problems/reorder-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        HashMap<ListNode, ListNode> map = new HashMap<>();
        ListNode pre = head, cur = head.next;
        ListNode tail = null;
        while(pre != null && cur != null) {
            map.put(cur, pre);
            pre = cur;
            cur = cur.next;
            if(cur == null) tail = pre;
        }
        ListNode left = head, right = tail;
        ListNode newHead = new ListNode();
        ListNode tmp = newHead;
        while(left != right) {
            tmp.next = left;
            ListNode next = left.next;
            left.next = right;
            tmp = right;
            tmp.next = null;
            if(next == right) break;
            left = next;
            right = map.get(right);
        }
        if(left == right) {
            tmp.next = left;
            left.next = null;
        }
        head = newHead.next;
    }
}